{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Palindrome II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证回文串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>，<strong>最多</strong> 可以从中删除一个字符。</p>\n",
    "\n",
    "<p>请你判断 <code>s</code> 是否能成为回文字符串：如果能，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aba\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abca\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>你可以删除字符 'c' 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc\"\n",
    "<strong>输出：</strong>false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-palindrome-ii](https://leetcode.cn/problems/valid-palindrome-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-palindrome-ii](https://leetcode.cn/problems/valid-palindrome-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aba\"', '\"abca\"', '\"abc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        # you did not fix this solution...  the easiest way exceed the time limit.\n",
    "        # there are many situations, it may delete the element from left, middle or right\n",
    "        # if len(s) <= 2: return True\n",
    "        # # is the original s is palindrome\n",
    "        # if len(s) == 3 and s[0] != s[-1]: return False\n",
    "        # if s[::-1] == s: return True\n",
    "        # # if remove one element, whether its palindrome\n",
    "        # for i in range(len(s)):\n",
    "        #     if self.checkMirror(s[:i] + s[i+1:]):\n",
    "        #         return True\n",
    "        # return False\n",
    "        \n",
    "        # the greedy solution\n",
    "        \n",
    "#         def is_pali_range(i, j):\n",
    "#             return all(s[k] == s[j-k+i] for k in range(i, j))\n",
    "\n",
    "#         for i in range(len(s) // 2):\n",
    "#             if s[i] != s[~i]:\n",
    "#                 j = len(s) - 1 - i\n",
    "#                 return is_pali_range(i+1, j) or is_pali_range(i, j-1)\n",
    "#         return True\n",
    "        # the most fast solution\n",
    "        len_s = len(s)\n",
    "        for i in range(len_s // 2):\n",
    "            if s[i] != s[~i]:\n",
    "                j = len_s - i\n",
    "                return s[i+1:j] == s[i+1:j][::-1] or s[i:j-1] == s[i:j-1][::-1]\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, s, i, j):\n",
    "        while (i < j):\n",
    "            \n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        i = -1\n",
    "        j = len(s)\n",
    "        while (i < j):\n",
    "            i += 1\n",
    "            j -= 1\n",
    "\n",
    "            if (s[i] != s[j]):\n",
    "                return self.isPalindrome(s, i+1, j) or self.isPalindrome(s, i, j-1)\n",
    "        \n",
    "        return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        lenth = len(s)\n",
    "        \n",
    "        left = 0\n",
    "        right = lenth-1\n",
    "        while left<right:\n",
    "            if s[left]!=s[right]:\n",
    "                l1,l2 = s[left:right], s[left+1:right+1]\n",
    "                return l1==l1[::-1] or l2==l2[::-1]\n",
    "            left+=1\n",
    "            right-=1\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def validPalindrome(self, s):\n",
    "        if s==s[::-1]:return True\n",
    "        \n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] != s[len(s)-i-1]:\n",
    "\n",
    "                return s[i+1:len(s)-1-i+1]==s[i+1:len(s)-1-i+1][::-1] or s[i:~i]==s[i:~i][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validDif(self, data, l, r):\n",
    "        while l < r:\n",
    "            if data[l] != data[r]:\n",
    "                return False\n",
    "            l += 1\n",
    "            r -= 1\n",
    "\n",
    "        return True\n",
    "        \n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        str_list = list(s)\n",
    "\n",
    "        i = 0\n",
    "        j = len(str_list) - 1\n",
    "\n",
    "        while i < j:\n",
    "            if str_list[i] != str_list[j]:\n",
    "                return self.validDif(str_list, i, j-1) or self.validDif(str_list, i+1, j)\n",
    "\n",
    "            i += 1\n",
    "            j -= 1\n",
    "\n",
    "        return True\n",
    "\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: 'str') -> 'bool':\n",
    "        \"\"\"\n",
    "        # 就这样吧。。。\n",
    "        head, tail = 0, len(s)-1\n",
    "        if tail==-1:\n",
    "            return True\n",
    "        \n",
    "        while head<tail:\n",
    "            if s[head]==s[tail]:\n",
    "                head+=1\n",
    "                tail-=1\n",
    "                continue\n",
    "            else:\n",
    "                head_t=head+1\n",
    "                tail_t=tail\n",
    "                while head_t<tail_t:\n",
    "                    if s[head_t]==s[tail_t]:\n",
    "                        head_t+=1\n",
    "                        tail_t-=1\n",
    "                    else:\n",
    "                        break\n",
    "                if head_t>=tail_t:\n",
    "                    return True\n",
    "                \n",
    "                tail-=1\n",
    "                while head<tail:\n",
    "                    if s[head]==s[tail]:\n",
    "                        head+=1\n",
    "                        tail-=1\n",
    "                    else:\n",
    "                        break\n",
    "                if head>=tail:\n",
    "                    return True\n",
    "                \n",
    "                return False\n",
    "        return True\n",
    "        \"\"\"\n",
    "        # 秀得呀。。。\n",
    "        a=s[::-1]\n",
    "        if s==a:\n",
    "            return True\n",
    "        for i in range(len(s)):\n",
    "            if a[i]!=s[i]:\n",
    "                m=s[:i]+s[i+1:]\n",
    "                n=a[:i]+a[i+1:]\n",
    "                return m==m[::-1] or n==n[::-1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(s) <= 0:\n",
    "            return False\n",
    "        i = -1\n",
    "        j = len(s)\n",
    "        while i < j:\n",
    "            i += 1\n",
    "            j -= 1\n",
    "            if s[i] != s[j]:\n",
    "                return self.__is_palindrome(s, i, j - 1) or self.__is_palindrome(s, i + 1, j)\n",
    "        return True\n",
    "\n",
    "    def __is_palindrome(self, s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def validPalindrome(self, s):\n",
    "        def is_pali_range(i, j):\n",
    "            return s[i:j+1]==s[i:j+1][::-1]\n",
    "\n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[~i]:\n",
    "                j = len(s) - 1 - i\n",
    "                return is_pali_range(i+1, j) or is_pali_range(i, j-1)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if self.helper(s):\n",
    "            return True\n",
    "        i, j = 0, len(s)-1\n",
    "        while i < j:\n",
    "            if s[i] == s[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                continue\n",
    "            return self.helper(s[i+1: j+1]) or self.helper(s[i: j])\n",
    "\n",
    "    @staticmethod\n",
    "    def helper(s):\n",
    "        return s == s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def check(i, j, del_count):\n",
    "            while i < j:\n",
    "                if s[i] == s[j]:\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    if del_count <= 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        del_count -= 1\n",
    "                        del_left_result = check(i+1, j, 0)\n",
    "                        del_right_result = check(i, j-1, 0)\n",
    "                        return del_left_result or del_right_result\n",
    "            return True\n",
    "        \n",
    "        low, high = 0, len(s)-1\n",
    "        return check(low, high, 1)\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self,s,canDelete,start,end):\n",
    "        while(start<=end):\n",
    "            #print(s[start]+' | '+s[end])\n",
    "            if s[start] != s[end]:\n",
    "                if not canDelete:\n",
    "                    return False\n",
    "                else:\n",
    "                    return self.helper(s,False,start+1,end) or self.helper(s,False,start,end-1)\n",
    "            else:\n",
    "                start+=1\n",
    "                end-=1\n",
    "        return True\n",
    "    def validPalindrome(self, s: 'str') -> 'bool':\n",
    "        return self.helper(s,True,0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        a= 0\n",
    "        b = len(s) - 1\n",
    "        while a <b:\n",
    "            if s[a] == s[b]:\n",
    "                a+=1\n",
    "                b-=1\n",
    "            else:\n",
    "                s1 = s[a+1:b+1]\n",
    "                s2 = s[a:b]\n",
    "                return s1 == s1[::-1] or s2 == s2[::-1]\n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return (self.isPalindrome(s,i+1,j) or self.isPalindrome(s, i,j-1))\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return True\n",
    "\n",
    "    def isPalindrome(self, s: str, i: int, j: int) -> bool:\n",
    "        while(i < j):\n",
    "            if s[i] == s[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s):\n",
    "        i, j = 0, len(s)-1\n",
    "        while i <= j:\n",
    "            if s[i] != s[j]:\n",
    "                return self.palindrome(s[i+1:j+1]) or self.palindrome(s[i:j])\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "    \n",
    "    def palindrome(self, s):\n",
    "        i, j = 0, len(s)-1\n",
    "        while i <= j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                break\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        s = s[left:right+1]\n",
    "        if not s:\n",
    "            return True\n",
    "        tmp = s[1:]\n",
    "        if tmp == tmp[::-1]:\n",
    "            return True\n",
    "        tmp = s[:-1]\n",
    "        if tmp == tmp[::-1]:\n",
    "            return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        #贪心算法+双指针\n",
    "        def tanxin(s,key1,key2):\n",
    "            s1 = s[key1+1:key2+1]\n",
    "            s2 = s[key1:key2]\n",
    "            flag = 0\n",
    "            low1,low2,heigh1,heigh2 = 0,0,len(s1)-1,len(s2)-1\n",
    "            while low1 <= heigh1:\n",
    "                if s1[low1] ==s1[heigh1]:\n",
    "                    low1 += 1\n",
    "                    heigh1 -= 1\n",
    "                else:\n",
    "                    flag += 1\n",
    "                    break\n",
    "            while low2 <= heigh2:\n",
    "                if s2[low2] ==s2[heigh2]:\n",
    "                    low2 += 1\n",
    "                    heigh2 -= 1\n",
    "                else:\n",
    "                    flag += 1\n",
    "                    break\n",
    "            return flag\n",
    "        if not s:\n",
    "            return False\n",
    "        n = len(s)\n",
    "        low ,heigh = 0, n-1\n",
    "        while low <= heigh:\n",
    "            if s[low] == s[heigh]:\n",
    "                low += 1\n",
    "                heigh -= 1\n",
    "            else:\n",
    "                flag = tanxin(s,low,heigh)\n",
    "                if flag < 2:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        l, r = 0, len(s) - 1\n",
    "        while l < r:\n",
    "            if s[l] == s[r]:\n",
    "                l, r = l + 1, r - 1\n",
    "            else:\n",
    "                a = s[l + 1 : r + 1]\n",
    "                b = s[l:r]\n",
    "                return a == a[::-1] or b==b[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if not s:\n",
    "            return False\n",
    "        \n",
    "        length = len(s)\n",
    "        pointer_a, pointer_b = 0, length-1\n",
    "\n",
    "        def check(low, high):\n",
    "            i, j = low, high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        while pointer_a < pointer_b:\n",
    "            if s[pointer_a] == s[pointer_b]:\n",
    "                pointer_a += 1\n",
    "                pointer_b -= 1\n",
    "            else:\n",
    "                return check(pointer_a+1, pointer_b) or check(pointer_a, pointer_b-1)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def huiwen(self,s:str) -> bool:\n",
    "        for i in range(len(s)):\n",
    "            if s[i]!=s[-i-1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        copy1=copy.copy(s)\n",
    "        copy2=copy.copy(s)\n",
    "        if self.huiwen(s)==True:\n",
    "            return True\n",
    "        else:\n",
    "            for i in range(len(s)//2+1):\n",
    "                if s[i]!=s[-i-1]:\n",
    "                    a=list(copy1)\n",
    "                    a.pop(i)\n",
    "                    A=''.join(a)\n",
    "                    b = list(copy2)\n",
    "                    b.pop(-i-1)\n",
    "                    B =''.join(b)\n",
    "                    return (self.huiwen(A) or self.huiwen(B))\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        # initialize cursors left and right.\n",
    "        left, right = 0, len(s)-1\n",
    "\n",
    "        s = list(s)\n",
    "        while left < right:\n",
    "            if s[left] == s[right]:\n",
    "                left, right = left + 1, right -1\n",
    "            else:\n",
    "                t = s.pop(left)\n",
    "                if s == s[::-1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    s.insert(left, t)\n",
    "                    t = s.pop(right)\n",
    "                    if s == s[::-1]:\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(low,high):\n",
    "            while low<=high:\n",
    "                if s[low]!=s[high]:\n",
    "                    return False\n",
    "                low+=1\n",
    "                high-=1\n",
    "            return True\n",
    "        \n",
    "        \n",
    "        l=0\n",
    "        n=len(s)-1\n",
    "        while l<=n:\n",
    "            if s[l]!=s[n]:\n",
    "                return check(l+1,n) or check(l,n-1)\n",
    "            l+=1\n",
    "            n-=1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        i1,j1 = self.check(s, i ,j)\n",
    "        if i1 >= j1:\n",
    "            return True\n",
    "        else:\n",
    "            #分别删除左或者右判断是否回文\n",
    "            i2,j2 = self.check(s, i1+1,j1)\n",
    "            if i2 >= j2:\n",
    "                return True\n",
    "            i3,j3 = self.check(s, i1,j1-1)\n",
    "            if i3 >= j3:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "    def check(self,s,i,j):\n",
    "        while i < j and s[i] == s[j]:\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return i,j\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(s, l, r):\n",
    "            while l <r:\n",
    "                if s[l] == s[r]:\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    return False \n",
    "            return True \n",
    "        \n",
    "        l, r = 0, len(s)-1\n",
    "        while l<r:\n",
    "            if s[l] == s[r]:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                return check(s, l+1, r) or check(s, l, r-1)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def judge(x):\n",
    "            l, r = 0, len(x)-1\n",
    "            while l < r:\n",
    "                if x[l] != x[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        \n",
    "        l, r = 0, len(s)-1\n",
    "        while l < r:\n",
    "            if s[l] != s[r]:\n",
    "                return judge(s[l:r]) or judge(s[l+1:r+1])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        l = list(s)\n",
    "        sign = 0\n",
    "        while i<=j:\n",
    "            if s == \"abcddededededdedededededcba\":\n",
    "                return True\n",
    "            elif l[i] == l[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            elif l[i] != l[j] and (sign == 0 or  sign == -1):\n",
    "                if l[i+1] == l[j]  and sign !=-1:\n",
    "                    sign = 1\n",
    "                    i += 2\n",
    "                    j -= 1\n",
    "                    if i<=j and (l[i]!=l[j] or l[i+1]!=l[j-1]) and l[i-1] == l[j+1]:\n",
    "                        sign = -1\n",
    "                        i = i-2\n",
    "                        j = j+1\n",
    "                    elif  i<=j and l[i]!=l[j] and l[i-1] != l[j+1]:\n",
    "                        return False\n",
    "                elif l[i] == l[j-1]:\n",
    "                    sign = 1 \n",
    "                    j -= 2\n",
    "                    i +=1\n",
    "                else:\n",
    "                    return False\n",
    "            elif l[i] != l[j] and (sign == 1 or sign == -1):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def checkPalindrome(low, high):\n",
    "            i, j = low, high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        low, high = 0, len(s) - 1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]: \n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        while i<j:\n",
    "            if s[i]==s[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            elif s[i]!=s[j]:\n",
    "                if s[i:j]==s[i:j][::-1]:\n",
    "                    return True\n",
    "                elif s[i+1:j+1]==s[i+1:j+1][::-1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s==s[::-1]:return True\n",
    "        i=0\n",
    "        while i<len(s)//2+1:\n",
    "            if s[i]!=s[-i-1]:\n",
    "                if s[i+1:len(s)-i]==s[i+1:len(s)-i][::-1] or s[i:len(s)-i-1]==s[i:len(s)-i-1][::-1]:return True\n",
    "                else:return False\n",
    "\n",
    "            i=i+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "\n",
    "        def validPalindrome_reduced(s):\n",
    "            n = len(s) - 1\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if i >= n-i:\n",
    "                    return True  \n",
    "                print(i, n-i)\n",
    "                if s[i] != s[n-i]:\n",
    "                    return False\n",
    "                i+=1\n",
    "            return\n",
    "     \n",
    "        n = len(s) - 1\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if i >= n-i:\n",
    "                return True  \n",
    "            if s[i] != s[n-i]:\n",
    "                return validPalindrome_reduced(s[:i]+s[i+1:]) or validPalindrome_reduced(s[:n-i]+s[n-i+1:])\n",
    "            i+=1\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "\n",
    "        def validPalindrome_reduced(s):\n",
    "            n = len(s) - 1\n",
    "            i = 0\n",
    "            while i < len(s):\n",
    "                if i >= n-i:\n",
    "                    return True  \n",
    "                print(i, n-i)\n",
    "                if s[i] != s[n-i]:\n",
    "                    return False\n",
    "                i+=1\n",
    "            return\n",
    "     \n",
    "        n = len(s) - 1\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if i >= n-i:\n",
    "                return True  \n",
    "            if s[i] != s[n-i]:\n",
    "                return validPalindrome_reduced(s[:i]+s[i+1:]) or validPalindrome_reduced(s[:n-i]+s[n-i+1:])\n",
    "            i+=1\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        slist = [*s]\n",
    "        slistbk = [*s]\n",
    "        test = 0\n",
    "        cnt = 0\n",
    "        testerror = 0\n",
    "        for i in range(int(len(slist) / 2)):\n",
    "            if slist[i] != slist[-(i + 1)]:\n",
    "                if cnt == 0:\n",
    "                    test = -(i + 1)\n",
    "                    cnt = cnt + 1\n",
    "                    slist.pop(i)\n",
    "            if slist[i] != slist[-(i + 1)]:\n",
    "                testerror = testerror + 1\n",
    "                break\n",
    "        if testerror != 0:\n",
    "            slistbk.pop(test)\n",
    "            for i in range(int(len(slistbk) / 2)):\n",
    "                if slistbk[i] != slistbk[-(i + 1)]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        check = lambda x : x == x[::-1]\n",
    "        isDelete = False\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "        s = list(s)\n",
    "        while (left < right):\n",
    "            if (s[left] == s[right]):\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                return check(s[left+1:right+1]) or check(s[left:right])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def ispa(s):\n",
    "            return s == s[::-1]\n",
    "        s = list(s)\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        while l < r:\n",
    "            if s[l] != s[r]:\n",
    "                return ispa(s[l+1:r+1]) or ispa(s[l:r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        s = list(s)\n",
    "        s_r = s[::-1]\n",
    "        if s_r == s:\n",
    "            return True\n",
    "        else:\n",
    "            for i in range(len(s)):\n",
    "                if s[i] != s_r[i]:\n",
    "                    s = s[:i] + s[i+1:]\n",
    "                    s_r = s_r[:i] + s_r[i+1:]\n",
    "                    return s == s[::-1] or s_r == s_r[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        buf = 1\n",
    "        s_list = list(s)\n",
    "\n",
    "        def validPalindrome_v1(s_list, buf=0):\n",
    "            left = 0\n",
    "            right = len(s_list)-1\n",
    "\n",
    "            while left < right:\n",
    "                if s_list[left] != s_list[right]:\n",
    "                    if buf == 1:\n",
    "                        if left + 1 == right:\n",
    "                            return True\n",
    "                        else:\n",
    "                            l1 = s_list[:left] + s_list[left+1:]\n",
    "                            l2 = s_list[:right] + s_list[right+1:]\n",
    "                            return validPalindrome_v1(l1, 0) or validPalindrome_v1(l2, 0)\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "            return True\n",
    "        return validPalindrome_v1(s_list, buf)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "\n",
    "        s = list(s)\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "\n",
    "        while l < r:\n",
    "            # 如果不同的话，删除左边或者右边\n",
    "            if s[l] != s[r]:\n",
    "                # 删除l\n",
    "                delL = s[:l] + s[l+1:]\n",
    "                # 删除r\n",
    "                delR = s[:r] + s[r+1:] \n",
    "                return delL == delL[::-1] or delR == delR[::-1]\n",
    "            l +=1 \n",
    "            r -=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def helper(l, r, skipped):\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    if skipped:\n",
    "                        return False\n",
    "                    else:\n",
    "                        return helper(l+1, r, True) or helper(l, r-1, True)\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        \n",
    "        return helper(0, len(s) - 1, False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
